148D - Bag of mice - CodeForces Solution


dp games math probabilities *1800

Please click on ads to support us..

Python Code:

def sol(w,b,ls):

	if(w==0):
		return 0
	elif(b==0):
		return 1
	if(b==2):
		return(w/(w+2) + (2/(2+w))*((1)/(w+1)))
	if(b==1):
		return(w/(w+b))
	if(ls[w][b] != -1):
		return(ls[w][b])
	prob = w/(w+b)
	prob += (b/(b+w))*((b-1)/(b+w-1))*(((b-2)/(w+b-2))*sol(w,b-3,ls)+(w/(w+b-2))*sol(w-1,b-2,ls))
	ls[w][b] = prob
	return prob


w,b = map(int,input().split())
ls = [[-1]*(b+1) for _ in range(w+1)]
print("%.9f" % sol(w,b,ls))

C++ Code:

#include <bits/stdc++.h>
using namespace std; 

int w, b; 
double dp[1005][1005][2]; // person and turn  

int main() {
    cin >> w >> b; 

    // BASE CASES 
    // either shitter wins 
    for(int i = 1; i <= w; i++) {
        dp[i][0][0] = 1;  // princess goes first 
        dp[i][0][1] = 0; 
    }

    for(int i = 0; i <= b; i++) {
        dp[0][i][0] = 0; // princess has no chance 
        dp[0][i][1] = 0; // dragon garunteed  
    }

    for(int i = 1; i <= w; i++) {
        dp[i][1][0] = ((double) i / (double) (i + 1)) + ((double) 1 / (double) (i + 1)) * dp[i - 1][0][1]; 
        dp[i][1][1] = ((double) 1 / (double) (i + 1)) * dp[i - 1][0][0];
        for(int j = 2; j <= b; j++) {
            double pWin = (double) i / (double) (i + j); 
            double pSad = (double) j / (double) (i + j); 

            double pWhite = (double) i / (double) (i + j - 1); 
            double pBlack = (double) (j - 1) / (double) (i + j - 1); 

            // cout << "WIN: " << pWin << '\n'; 

            dp[i][j][0] = pWin + pSad * dp[i][j - 1][1];  
            dp[i][j][1] = pSad * (pWhite * dp[i - 1][j - 1][0] + pBlack * dp[i][j - 2][0]);
            // cout << dp[i][j][0] << ' '; 
        }
        // cout << '\n'; 
    }

    cout << setprecision(10) << dp[w][b][0] << '\n'; 

}


Comments

Submit
0 Comments
More Questions

470. Implement Rand10() Using Rand7()
866. Prime Palindrome
1516A - Tit for Tat
622. Design Circular Queue
814. Binary Tree Pruning
791. Custom Sort String
787. Cheapest Flights Within K Stops
779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST
445. Add Two Numbers II
442. Find All Duplicates in an Array
437. Path Sum III
436. Find Right Interval
435. Non-overlapping Intervals
406. Queue Reconstruction by Height
380. Insert Delete GetRandom O(1)
332. Reconstruct Itinerary
368. Largest Divisible Subset
377. Combination Sum IV
322. Coin Change
307. Range Sum Query - Mutable
287. Find the Duplicate Number